GATE CSE 2021 SET-1
Q41.
Consider the relation R(P,Q,S,T,X,Y,Z,W) with the following functional dependencies. PQ\rightarrow X;\quad P\rightarrow YX;\quad Q\rightarrow Y; \quad Y\rightarrow ZW Consider the decomposition of the relation R into the constituent relations according to the following two decomposition schemes. D1:\quad R=[(P,QS,T);\;(P,T,X);\;(Q,Y);\;(Y,Z,W)] D2:\quad R=[(P,Q,S);\;(T,X);\;(Q,Y);\;(Y,Z,W)] Which one of the following options is correct?Q42.
Consider the following array.\begin{array}{|l|l|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array} Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?Q43.
Consider the following statements. S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree.Which one of the following options is correct?Q44.
A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?Q45.
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code\begin{array}{lll} P & \rightarrow & D^* E^* \\ D & \rightarrow & \textsf{int ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ int\}} \\ D & \rightarrow & \textsf{bool ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ bool\}} \\ E& \rightarrow & E_1 +E_2 \{ \text{check that } E_1. \text{type}=E_2. \text{type} = \textsf{int}; \text{set } E.\text{type }:= \textsf{int} \} \\ E & \rightarrow & !E_1 \{ \text{check that } E_1. \text{type} = \textsf{bool}; \text{ set } E.\text{type} := \textsf{bool} \} \\ E & \rightarrow & \textsf{ID} \{ \text{set } E. \text{type } := \textsf{int} \} \end{array} With respect to the above grammar, which one of the following choices is correct?Q46.
Let G=(V,E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \} Let M be the adjacency matrix of G. Define graph G_2 on the same set of vertices with adjacency matrix N, where N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right. Which one of the following statements is true?Q47.
Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s=pop(); Consider the following sequence of operations on an empty queue. enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q=dequeue(); The value of s+q is ___________.Q48.
Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?[MSQ]Q49.
Let r_i(z) and w_i(z) denote read and write operations respectively on a data item z by a transaction T_i. Consider the following two schedules. S1: r_1(x)r_1(y)r_2(x)r_2(y)w_2(y)w_1(x) S2: r_1(x)r_2(x)r_2(y)w_2(y)r_1(y)w_1(x) Which one of the following options is correct?Q50.
Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?